Лемма об удалении моста

Удаление моста увеличивает число компонент связности графа $G$ ровно на 1.

Пусть $G_e$ — компонента связности графа $G$, содержащая мост $e = (u, v)$. Все компоненты $G$, кроме $G_e$, переходят в граф $G-e$ без изменения. Следовательно, достаточно показать, что в графе $G_e - e$ две компоненты связности. Докажем, что любая вершина $w \in G_e$ связана в $G_e - e$ либо с $u$, либо с $v$. Так как $G_e$ связен, то существует $(w, u)$-путь $P$. Если $e \notin P$, то $w$ и $u$ связаны в $G_e - e$. Если же $e \in P$, то путь $P$ имеет вид $(w, e_1, \dots, v, e, u)$, и следовательно $w$ и $v$ связаны в $G_e - e$. $\square$